/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    const queue = []
    let front = 0, rear = 0, levelPos = 0
    let pre = new Node()
    queue.push(root)
    rear++
    levelPos++
    let res = []
    let arr = []
    while(queue.length > 0) {
        const temp = queue.shift()
        arr.push(temp)
        pre.next = temp
        pre = temp
        front++
        if(temp.left) {
            queue.push(temp.left)
            rear++
        }
        if(temp.right) {
            queue.push(temp.right)
            rear++
        }
        if(front === levelPos) {
            levelPos = rear
            res.push(arr)
            arrr = []
        }
    }
    for(let i = 0; i < res.length; i++) {
        for(let j = 0; j < res[i].length - 1; j++) {
            res[i][j].next = res[i][j + 1]
        }
    }
    return res[0][0]
};
// 这个层序遍历的方法记一下
var connect = function (root) {
    if (root === null) {
        return null;
    }
    let q = [root];
    while (q.length) {
        const tmp = q;
        q = [];
        for (let i = 0; i < tmp.length; i++) {
            const node = tmp[i];
            if (i) { // 连接同一层的两个相邻节点
                tmp[i - 1].next = node;
            }
            if (node.left) {
                q.push(node.left);
            }
            if (node.right) {
                q.push(node.right);
            }
        }
    }
    return root;
};